1. Field of the Invention
The present invention relates generally to telecommunications. More particularly, the present invention relates to DSL modems utilizing low density parity check (LDPC) codes and methods of simply generating such LDPC codes.
2. State of the Art
LDPC codes were invented by R. Gallager in 1963. R. G. Gallager, xe2x80x9cLow-Density-Parity-Check Codesxe2x80x9d, MIT Press, Cambridge, Mass. 1963. Over thirty years later, a number of researchers showed that LDPC code is a constructive code which allows a system to approach the Shannon limit. See, e.g., D. J. C. MacKay and R. M. Neal, xe2x80x9cNear Shannon limit performance of LDPC codesxe2x80x9d, Electron. Letters, Vol. 32, No. 18, August 1996; D. J. C. MacKay, xe2x80x9cGood Error-Correcting Codes Based on Very Sparse Matricesxe2x80x9d, IEEE Transactions on Information Theory, Vol. 45, No. 2, March 1999; D. J. C. MacKay, Simon T. Wilson, and Matthew C. Davey, xe2x80x9cComparison of Constructions of Irregular Gallager Codesxe2x80x9d, IEEE Transactions on Communications, Vol. 47, No. 10, October 1999; Marc P. C. Fossorier, Miodrag Michaljevic, and Hideki Imai, xe2x80x9cReduced Complexity Iterative Decoding of LDPC Codes Based on Belief Propagationxe2x80x9d, IEEE Transactions on Communications, Vol. 47, No. 5, May 1999; E. Eleftheriou, T. Mittelholzer, and A. Dholakia, xe2x80x9cReduced-complexity decoding algorithm for LDPC codesxe2x80x9d, Electron. Letter, Vol. 37, January 2001. Indeed, these researchers have proved that LDPC code provides the same performance as Turbo-code and provides a range of trade-offs between performance and decoding complexity. As a result, several companies have suggested that LDPC code be used as part of the G.Lite.bis and G.dmt.bis standards. IBM Corp., xe2x80x9cLDPC codes for G.dmt.bis and G.lit.bisxe2x80x9d, ITU-Telecommunication Standardization Sector, Document CF-060, Clearwater, Fla., Jan. 8-12, 2001; Aware, Inc., xe2x80x9cLDPC Codes for ADSLxe2x80x9d, ITUxe2x80x94Telecommunication Standardization Sector, Document BI-068, Bangalore, India, Oct. 23-27, 2000; IBM Corp., xe2x80x9cLDPC codes for DSL transmissionxe2x80x9d, ITUxe2x80x94Telecommunication Standardization Sector, Document BI-095, Bangalore, India, Oct. 23-27, 2000; IBM Corp., xe2x80x9cLDPC coding proposal for G.dmt.bis and G.lite.bisxe2x80x9d, ITUxe2x80x94Telecommunication Standardization Sector, Document CF-061, Clearwater, Fla., Jan. 8-12, 2001; IBM Corp., Globespan, xe2x80x9cG.gen: G.dmt.bis: G.Lite.bis: Reduced-complexity decoding algorithm for LDPC codesxe2x80x9d, ITUxe2x80x94Telecommunication Standardization Sector, Document IC-071, Irvine, Calif., Apr. 9-13, 2001.
LDPC code is determined by its check matrix H. Matrix H is used in a transmitter (encoder) for code words generation and in a receiver (decoder) for decoding the received code block. The matrix consists of binary digits 0 and 1 and has size Mk*Mj, where Mk is the number of columns, and Mj is the number of rows. Each row in the matrix defines one of the check equations. If a xe2x80x9c1xe2x80x9d is located in the k-th column of the j""th row, it means that the k-th bit of the code block participates in the j-th check equation.
Matrix H is a xe2x80x9csparsexe2x80x9d matrix in that it does not have many xe2x80x9conesxe2x80x9d. Generally, the matrix contains a fixed number of xe2x80x9conesxe2x80x9d N in each column and a fixed number of xe2x80x9conesxe2x80x9dNk in each row. In this case, design parameters should preferably satisfy the equation:
Mk*Nj=Mj*Nkxe2x80x83xe2x80x83(1)
Although it is convenient to have equal numbers of xe2x80x9conesxe2x80x9d in each column and in each row, this is not an absolute requirement. Some variations of design parameters Nk and Nj are permissible; i.e., Nk(j) and Nj(k) can be functions of j and k, correspondingly. In addition, another important constraint for matrix design is that the matrix should not contain any rectangles with xe2x80x9conesxe2x80x9d in the vertices. This property is sometimes called xe2x80x9celimination of cycles with length 4xe2x80x9d or xe2x80x9c4-cycle eliminationxe2x80x9d. For purposes herein, it will also be called xe2x80x9crectangle eliminationxe2x80x9d.
Generally, there are two approaches in the prior art to designing H matrices. The first approach was that proposed by Gallager in his previously cited seminal work, R. G. Gallager, xe2x80x9cLow-Density-Parity-Check Codesxe2x80x9d, MIT Press, Cambridge, Mass. 1963, and consists of a random distribution of Nj ones within each matrix column. This random distribution is carried out column by column, and each step is accompanied by rectangle elimination within the current column relative to the previous columns. The second approach to H-matrix design is based on a deterministic procedure. For example, in the previously cited IBM Corp., xe2x80x9cLDPC codes for G.dmt.bis and G.lit.bisxe2x80x9d, ITUxe2x80x94Telecommunication Standardization Sector, Document CF-060, Clearwater, Fla., Jan. 8-12 2001, a deterministic H-matrix construction is proposed which includes identity matrices and powers of an initial square permutation matrix.
Both of the prior art approaches to designing H matrices have undesirable characteristics with respect to their implementation in DSL standards. In particular, the random distribution approach of Gallager is not reproducible (as it is random), and thus, the H matrix used by the transmitting modem must be conveyed to the receiving modem. Because the H matrix is typically a very large matrix, the transfer of this information is undesirable. On the other hand, while the deterministic matrix of IBM is reproducible, it is extremely complex and difficult to generate. Thus, considerable processing power must be dedicated to generating such a matrix, thereby adding complexity and cost to the DSL modem. Besides, this approach does not allow constructing a matrix with arbitrary design parameters Mk and Mj. 
It is therefore an object of the invention to provide simple methods of generating reproducible H matrices.
It is another object of the invention to provide DSL modems which utilize simply generated reproducible H matrices.
In accord with these objects which will be discussed in detail below, the DSL modem of the invention generally includes a receiver and a transmitter with the transmitter including a substantially deterministic LDPC encoder. The encoder is a function of a substantially deterministic H matrix (H=A|B) which is determined according to the steps and rules set forth below. More particularly, the encoder takes a block of bits and utilizes a generation matrix G=Axe2x88x921B which is derived from (i.e., is a function of) the H matrix in order to generate redundant parity bits. The redundant bits are appended to the original block of bits to generate a word.
The substantially deterministic H matrix is determined as follows. First, the xe2x80x9conesxe2x80x9d of a first column N are assigned randomly or deterministically. Preferably, the ones are distributed evenly within the first column with the first xe2x80x9c1xe2x80x9d in the first row of the first column according to the algorithm:
H(r,1)=1, where r=1+(ixe2x88x921)*integer (Mj/Nj); i=1,2, . . . Njxe2x80x83xe2x80x83(2)
Then, beginning with the second column, assignment of xe2x80x9conesxe2x80x9d is carried out deterministically with each xe2x80x9c1xe2x80x9d in a previous (ancestor) column generating a xe2x80x9c1xe2x80x9d in the next (descendant) column based on the rule that a descendant is placed one position below or one position above an ancestor (it being determined in advance by convention whether the position below is used or the position above is used). As a result, a descending diagonal or an ascending diagonal is generated. Where a descending diagonal is used and the ancestor is in the lowest row of the matrix, the descendant may take any position in the next column, although it is preferable to place the descendant in the highest free position.
When distributing xe2x80x9conesxe2x80x9d in any given column, each new descendant should be checked to ensure that no rectangles are generated in conjunction with other xe2x80x9conesxe2x80x9d in the current column and previous columns. If a rectangle is generated, the location of the descendant is changed, preferably by shifting the location down or up (by convention) one position at a time until the descendant is in a position where no rectangle is generated. If the position is shifted down and the lowest position is reached without finding a suitable position, the search is continued by shifting the location one position up from the initial descendant position until a suitable position is found.
According to the invention, the descendants may be generated in any given order. Two preferable generation orders correspond to increasing or decreasing ancestor positions in the column. For example, descendants may be generated by first generating a descendant for the ancestor at the bottom of the matrix, then by generating a descendant for the ancestor above that in the column, then by generating a descendant for the ancestor above that one, etc. (also called herein xe2x80x9cbottom-upxe2x80x9d); or by first generating a descendent for the ancestor at the top of the matrix, then by generating a descendant for the ancestor below that in the column, then by generating a descendant for the ancestor below that one, etc. (also called herein xe2x80x9ctop-downxe2x80x9d).
When generating descendants it is possible that one or more descendants can xe2x80x9cdisappearxe2x80x9d because of the lack of free positions satisfying the rectangle elimination criterium. To regenerate the xe2x80x9clost descendantxe2x80x9d, it is generally sufficient to change the order of descendant generation for that column. Thus, if the order of descendant generation was conducted xe2x80x9cbottom-upxe2x80x9d, the direction of generation is switched to xe2x80x9ctop-downxe2x80x9d and vice versa; preferably for that column only. If changing the order of descendant generation in a column does not cause a free position to appear, the descendant disappears for that column.
When a descendant disappears it is desirable in the next column to provide a new descendant which does not have an ancestor. In this case, a search of an acceptable position for an xe2x80x9cancestor-lessxe2x80x9d descendant is conducted, preferably from the first row down.
Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures.